10058. Поиск в ширину 0 – 1 – 2

Задан неориентированный граф. Вес его ребер может принимать только значения 0, 1 или 2. Найдите кратчайшее расстояние между вершинами s и d.

Вход. Первая строка содержит четыре целых числа: количество вершин n, количество ребер m (n, m ≤ 10⁵) и номера вершин s и d (1 ≤ s, d ≤ n). Каждая из следующих m строк содержит три целых числа a, b и w задающих неориентированное ребро (a, b) весом w (0 ≤ w ≤ 2).

Выход. Выведите кратчайший путь между вершинами s и d.

Пример входа	Пример выхода
5 5 1 4 1 2 1 2 3 0 3 4 2 1 5 2 4 5 2	3

РЕШЕНИЕ

поиск в ширину

Анализ алгоритма

Для каждого ребра (u, v) весом 2 введем фиктивную вершину p и заменим его двумя ребрами весом 1: (u, p) и (p, v). Изначально вершины нрафа пронумерованы числами 1, 2, …., n. Фиктивными будем объявлять вершины n + 1, n + 2, … . Поскольку ребер в графе существует не более m, то и фиктивных вершин будет не более m.

Задача сведена к использованию поиска в ширину на 0 – 1 графе.

Пример

Граф, приведенный в примере, показан слева. Для каждого ребра весом 2 вводим фиктивную вершину (вершины 6, 7, 8 - фиктивные). Справа приведен 0 – 1 граф.

Реализация алгоритма

Объявим константу бесконечность.

#define INF 0x3F3F3F3F

Объявим массив кратчайших расстояний dist и список смежности графа g.

vector<int> dist;

vector<vector<pair<int, int> > > g;

Функция bfs реализует поиск в ширину на 0 – 1 графе из вершины start.

void bfs(int start)

{

dist = vector<int>(n + 1, INF);

dist[start] = 0;

deque<int> q;

q.push_back(start);

while (!q.empty())

{

int v = q.front(); q.pop_front();

for (int i = 0; i < g[v].size(); i++)

{

int to = g[v][i].first;

int w = g[v][i].second;

if (dist[to] > dist[v] + w)

{

dist[to] = dist[v] + w;

if (w == 1)

q.push_back(to);

else

q.push_front(to);

}

}

}

}

Основная часть программы. Читаем входные данные. Строим граф.

scanf("%d %d %d %d", &n, &m, &s, &d);

В результирующем графе с учетом фиктивных вершин будет не более n + m.

g.resize(n + m + 1);

for (i = 0; i < m; i++)

{

scanf("%d %d %d", &a, &b, &w);

if (w <= 1)

{

g[a].push_back(make_pair(b, w));

g[b].push_back(make_pair(a, w));

}

else

{

Обрабатываем ребро длины 2. Вводим фиктивную вершину, увеличиваем количество вершин на 1.

n++;

Проводим неориентированные ребра (a, n), (n, b) весом 1.

g[a].push_back(make_pair(n, 1));

g[n].push_back(make_pair(b, 1));

g[b].push_back(make_pair(n, 1));

g[n].push_back(make_pair(a, 1));

}

}

Запускаем поиск в ширину из стартовой вершины s.

bfs(s);

Выводим кратчайший путь до вершины d.

printf("%d\n", dist[d]);